package datastructure.book.tujiesuanfa.queueastack.solution._4_error;

import java.util.LinkedList;

public class Solution1 {
    /**
     * putIn入栈序列，takeOut出栈序列，判断出栈序列是否合法
     * 栈中元素值各不相同，putIn 是 takeOut 的排列。
     * putIn = [6,7,8,9,10,11], takeOut = [9,11,10,8,7,6]
     * true
     * push(6), push(7), push(8), push(9), pop() -> 9,
     * push(10), push(11),pop() -> 11,pop() -> 10, pop() -> 8, pop() -> 7, pop() -> 6
     */
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if (putIn == null || putIn.length < 2) {
            return true;
        }
        LinkedList<Integer> mockStack = new LinkedList<>();
        int top = 0;
        for (int i : putIn) {
            if (i != takeOut[top]) {
                mockStack.add(i);
            } else {
                top++;
                while (top < takeOut.length && mockStack.peekLast()!=null&& mockStack.peekLast().equals(takeOut[top]) ) {
                    mockStack.removeLast();
                    top++;
                }
            }
        }
        return mockStack.isEmpty();
    }
}
